#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <functional>
#include <mutex>
#include <chrono>
#include <thread>
#include <condition_variable>
#include <assert.h>
using namespace std;

typedef long long lint;

class ZeroEvenOdd {
private:
    int n;
    int cur=0;
    mutex mu;
    condition_variable cv;

public:
    ZeroEvenOdd(int n) {
        this->n = n;
    }

    // printNumber(x) outputs "x", where x is an integer.
    void zero(function<void(int)> printNumber) {
        int cnt=0;
        do{std::unique_lock<std::mutex> lck(mu);
            while(cur%2 != 0) cv.wait(lck);
            printNumber(0);
            cur++;
            cv.notify_all();
            cnt++;}
        while(cnt<n);
    }

    void odd(function<void(int)> printNumber) {
        int next=1;
        while(next <= n) {
            std::unique_lock<std::mutex> lck(mu);
            while(cur%4 != 1 ) cv.wait(lck);
            printNumber(next);
            cur++;
            cv.notify_all();
            next += 2;
        }

    }

    void even(function<void(int)> printNumber) {
        int next=2;
        while(next <= n) {
            std::unique_lock<std::mutex> lck(mu);
            while(cur%4 != 3 ) cv.wait(lck);
            printNumber(next);
            cur++;
            cv.notify_all();
            next += 2;
        }
    }
};

void printnumber(int n){cerr<<n;}

ZeroEvenOdd zeo(1);
void zero(){zeo.zero(printnumber);}
void even(){zeo.even(printnumber);}
void odd(){zeo.odd(printnumber);}

int main()
{

    auto zerop = std::thread(zero);
    auto evenp = std::thread(even);
    auto oddp = std::thread(odd);

    zerop.join();
    evenp.join();
    oddp.join();
}


